package com.carl.leetcode.pointer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by carlXie on 2016/1/18.
 * email: kkrimen@gmail.com
 */
public class ThreeSum {
    public static void main(String[] args) {
        int[] nums = new int[]{7,-1,14,-12,-8,7,2,-15,8,8,-8,-14,-4,-5,7,9,11,-4,-15,-6,1,-14,4,3,10,-5,2,1,6,11,2,-2,-5,-7,-6,2,-15,11,-6,8,-4,2,1,-1,4,-6,-15,1,5,-15,10,14,9,-8,-6,4,-6,11,12,-15,7,-1,-9,9,-1,0,-4,-1,-12,-2,14,-9,7,0,-3,-4,1,-2,12,14,-10,0,5,14,-1,14,3,8,10,-8,8,-5,-2,6,-11,12,13,-7,-12,8,6,-13,14,-2,-5,-11,1,3,-6};
        List<List<Integer>> resultList = threeSum(nums);
        for (int i = 0; i < resultList.size(); i ++) {
            for (int j = 0; j < resultList.get(i).size(); j++) {
                System.out.printf(resultList.get(i).get(j) + " ");
            }
            System.out.println();
        }
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> resultList = new ArrayList<List<Integer>>();

        for (int i = 0; i < nums.length; i++) {
            int target = -nums[i];
            int front = i + 1;
            int rear = nums.length - 1;

            while(front < rear) {
                int sum = nums[front] + nums[rear];
                if(sum < target) {
                    ++ front;
                } else if(sum > target) {
                    -- rear;
                } else {
                    List<Integer> subList = Arrays.asList(nums[i], nums[front], nums[rear]);
                    resultList.add(subList);

                    // avoid duplicate solution
                    while(front < rear && nums[front] == subList.get(1)) {
                        ++ front;
                    }
                    while(front < rear && nums[rear] == subList.get(2)) {
                        -- rear;
                    }
                }
            }
        }

        return resultList;
    }
}
